// 单项链表
/*
class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

class LinkedList {
    constructor() {
        this.head = new Node('head')
    }

    insert(newElement, item) {
        let current = this.find(item)
        let newNode = new Node(newElement)
        newNode.next = current.next // 先把后面的链条接上
        current.next = newNode      // 再接上前面的链条
    }

    add(newElement) {
        this.insert(newElement)
    }

    find(item) {
        let current = this.head
        while (current.element !== item) {
            if (current.next === null) {
                return current
            }
            current = current.next
        }
        console.log(current)
        return current
    }

    findPrev(item) {
        let current = this.head
        while (current.next && current.next.element !== item) {
            current = current.next
        }
        return current
    }

    remove(item) {
        let current = this.findPrev(item)
        current.next = current.next.next
        return item
    }

    findLast() {
        let current = this.head
        while (current.next !== null) {
            current = current.next
        }
        return current
    }

    log() {
        let current = this.head
        while (current.next) {
            current = current.next
            console.log(current.element)
        }
    }
} */

// 双向链表
/*
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        this.prev = null
    }
}

class LinkedList {
    constructor() {
        this.head = new Node('head')
    }

    insert(newElement, item) {
        let newNode = new Node(newElement)
        let current = this.find(item)

        // 接上链条
        newNode.next = current.next
        current.next = newNode

        // 维护当前节点的父及
        newNode.prev = current
        
        // 维护下个节点的 prev
        if (newNode.next) {
            newNode.next.prev = newNode
        }
    }

    find(item) {
        let current = this.head
        while (current && current.element !== item) {
            current = current.next
        }
        return current
    }

    findLast() {
        let current = this.head
        while(current.next !== null) {
            current = current.next
        }
        return current
    }

    add(item) {
        let newNode = new Node(item)
        let lastNode = this.findLast()
        lastNode.next = newNode
        newNode.prev = lastNode
    }

    remove(item) {
        let current = this.find(item) // 当前节点
        let prevNode = current.prev   // 父节点
        prevNode.next = current.next
        if (current.next) {
            current.next.prev = prevNode
        }
        current.next = null
        current.prev = null
        return true
    }

    log() {
        let current = this.head
        while (current.next) {
            current = current.next
            console.log(current.element)
        }
    }
}
 */

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

class LinkedList {
    constructor() {
        this.head = new Node('head')
        this.head.next = this.head
    }

    find(item) {
        let current = this.head
        while (
            current && 
            current.element !== item &&     // 定位某一个元素
            current.next.element !== 'head' // 链表走一圈的标记
        ) {
            current = current.next
        }
        return current
    }

    insert(newElement, item) {
        let newNode = new Node(newElement)
        let current = this.find(item)
        newNode.next = current.next
        current.next = newNode
    }

    add(item) {
        let lastNode = this.findLast()
        this.insert(item, lastNode)
    }

    findPrev(item) {
        let current = this.head
        while (
            current.next.element !== item && 
            current.next.element !== 'head'
        ) {
            current = current.next
        }
        return current
    }

    remove(item) {
        let prevNode = this.findPrev(item)
        prevNode.next = prevNode.next.next
    }

    findLast() {
        let current = this.head
        while (current.next.element !== 'head') {
            current = current.next
        }
        return current
    }

    log() {
        let current = this.head
        while (current.next.element !== 'head') {
            current = current.next
            console.log(current.element)
        }
        return current
    }
}

module.exports = LinkedList
